#include "range_coder.hpp"

#include <gvl/support/bits.hpp>

#if BIJECTIVE

uint64 canonicalEnd(uint64 low, uint32 range)
{
	// We seek the number of lower bits we can flip to
	// 0. This turns out to be floor(log2(range)).
	// First, we can at most add (range-1). A bit-pattern x
	// that has floor(log2(x)) == N can cancel at least N lower bits
	// of low. The one case where it can cancel more is when
	// the bit-pattern is all ones. We can take that into
	// account by incrementing x, effectively incrementing
	// floor(log2(x)) by 1 for all-1 bit-patterns. Since
	// we already subtracted 1 from range, we can simply
	// remove that subtraction and use plain floor(log2(range)).

#if 0
	// EXCEPTION: If range == 1, we can't change low at all,
	// so there will be no propagating carry.
	if(range <= 1)
		return low;

	int sh = gvl_log2(range);
	uint32 carry = 1<<sh;
#elif 0
	// Round down to a power of two
	// This assumes range >= 0x1000000, limiting the result to 2^n, n in [24, 31]
	carry = range - 1;
	carry |= carry >> 1;
	carry |= carry >> 2;
	carry |= carry >> 4;
	carry |= 0xffffff; // We only smear 8 bits, need to make sure 0..23 are 1.
	carry = (carry >> 1) + 1;

	// TODO: Find a way to integrate this case
	if((low & (0-carry)) == 0)
		return low;

	// Cancel bits and add carry
	return (low & (0-carry)) + carry; // (0-carry) == ~(carry-1)

#else
	// Assumes range >= 0x1000000
	uint32 top = ((range - 1) >> 1) | 0xffffff;
   
	top |= top >> 4;
	top |= top >> 2;
	top |= top >> 1;

	uint64 r = (low + top) & (0ull-top-1);

	if(r == 0) r = top + 1;
	return r;
#endif
}


uint64 Coder1::computeEnd(uint64 low, uint32 range, uint64 prev)
{
	uint64 high = low + range;
	if(!prev)
		return canonicalEnd(low, range);

	uint64 bottom = prev & (0 - prev);

	prev += bottom << 1;
	while(prev >= high)
	{
		uint64 offset = bottom >> 1;
		prev = low + offset;
		prev = (prev + bottom - 1) & (0 - bottom);
		prev -= offset;
		bottom >>= 1;
	}
   
	return prev;
}

uint32 smeardown(uint32 x)
{
	x |= x >> 16;
	x |= x >> 8;
	x |= x >> 4;
	x |= x >> 2;
	x |= x >> 1;
	return x;
}

uint32 extract_top_bit(uint32 x)
{
	unsigned long sh = 0;
	_BitScanReverse(&sh, x);

	return 1 << sh;
}

uint32 canonicalEnd3(uint32 low, uint32 range)
{
#if 0
	uint32 top = (range >> 1);

	top |= top >> 16;
	top |= top >> 8;
	top |= top >> 4;
	top |= top >> 2;
	top |= top >> 1;

	uint32 r = (low + range - 1) & (~top);
	++top;
	if(r & top) r -= top;
	return r;
#else
	uint32 high = low + range - 1;

	uint32 t = extract_top_bit(low ^ high);

	uint32 ret = (low & (0-t)) | t; // (high & t) == 1 && (low & t) == 0, since this is the top differing bit, and low < high

	assert(ret >= low && ret <= high);

	return ret;
#endif
}


uint32 Coder3::computeEnd3(uint32 low, uint32 range, uint32 prev)
{
	if(!prev)
		return canonicalEnd3(low, range);

	uint32 high = low + range - 1;

	uint32 bottom = prev & (0 - prev);

#if 0
	uint64 prev64 = prev;
	prev64 += uint64(bottom) << 1;
	while(prev64 > high)
	{
		uint32 offset = bottom >> 1;
		prev64 = low + offset;
		prev64 = (prev64 + bottom - 1) & (0 - bottom);
		prev64 -= offset;
		bottom >>= 1;
	}
#elif 0
	uint64 prev64 = prev;
	prev64 += uint64(bottom) << 1;
	while(prev64 > high)
	{
		uint32 mask = (0 - bottom);
		bottom >>= 1;
		prev64 = ((low + bottom - 1) & mask) + bottom; // (bottom - (bottom >> 1) == bottom) assumes (bottom > 1)
	}

	return uint32(prev64);
#else
	uint32 ret = prev;
	ret += bottom << 1;
	if(ret <= high && ret > prev)
		return ret;

	while(true)
	{
		uint32 diverging = smeardown(low ^ high);
		//possible &= ~low | (low & (0-low)); // Exclude impossible due to underflowing

		uint32 first_diff = (diverging + 1) >> 1; // First differing bit

		// Allow stop-bit on first_diff and all bits on or after the first 0-bit after that.
		// The reason is that we need a zero-bit to catch any carry from underflow adjustment done
		// in the last step so that we don't overflow instead. Overflowing only happens if
		// high has a zero-bit
		uint32 allowed_after = smeardown((~low) & (diverging >> 1));
		uint32 possible = first_diff | allowed_after; // Possible without overflowing

		possible &= bottom - 1; // Exclude reserved lengths

		assert(possible != 0);

		uint32 next = extract_top_bit(possible);

		ret = ((low + next - 1) & (0 - next)) | next;

		assert(ret >= low);

		if(ret <= high)
			return ret;

		bottom >>= 1;
	}
#endif
   
	
}

uint64 shiftPrevEnd(uint64 low, uint64 prev)
{
	if((prev >> 24) > (low >> 24) && (prev & 0xffffff))
	{
		prev = static_cast<unsigned int>(prev) << 8;
		prev = (0 - (prev & (0 - prev))) & 0xffffffff;
	}
	else if((prev >> 24) < (low >> 24))
		prev = 0; // All reserved are outside range
	else
		prev = static_cast<unsigned int>(prev) << 8;

	return prev;
}

uint32 Coder3::shiftPrevEnd3(uint32 low, uint32 prev)
{
	// If (prev & 0xffffff) == 0, we discard all reserved ends as
	// none can appear again.
	// [1] If MSB(prev) < MSB(low), we know that ends before
	// (prev & 0xffffff) have been discarded or reserved. But
	// (prev & 0xffffff) itself cannot have been visited. Decrement it.

	// [2] If MSB(prev) == MSB(low), we know that (prev & 0xffffff) has
	// been reserved. Keep it as is.

	// [3] If MSB(prev) > MSB(low), we know all ends of this length
	// has been visited, so jump to the last end of the current length.

	uint32 n = prev << 8;

	if((prev >> 24) != (low >> 24))
	{
		uint32 bottom = n & (0 - n);

		if((prev >> 24) > (low >> 24))
		{
			// Smear bits up
			return 0-bottom;
		}
		else
		{
			// Decrement
			uint64 r = uint64(n) - bottom - bottom;
			return (r & 0xffffffff) << -(r >> 32); // Left-shift on underflow
		}
	}

	return n;
}
#endif

void __declspec(noinline) Coder1::shift()
{
	if ((low ^ 0xff000000) >= (1 << 24))
	{
		unsigned int c = static_cast<unsigned int>(low >> 32);

		if(!skip) writer.put(buffer + c);
		else skip = false;

		--c;
		for (; help > 0; help--)
			writer.put(c);
		buffer = static_cast<unsigned int>(low) >> 24;
	}
	else
	{
		help++;
	}

#if BIJECTIVE
	// if (low >> 24) < (prevEnd >> 24):
	// All carry-over bits have already been used with
	// this prefix. We need to add another bit.
      
	prevend = shiftPrevEnd(low, prevend);
#endif

	low = static_cast<unsigned int>(low) << 8;

}